home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / wais / ir / DESIGN < prev    next >
Text File  |  1995-05-09  |  4KB  |  96 lines
  1.  
  2.  
  3.               Serial Indexer Overview
  4.                   Brewster Kahle
  5.  
  6. The serial indexer is a simple inverted file system that is not very
  7. different from existing IR systems.
  8.  
  9. DATABASE FILES
  10.  
  11. The serial indexer parses files and creates an inverted file index made up
  12. of 7 files.  For a database named "index" the files would be:
  13.  *  index.inv -- the "postings file" that is a term followed by a list of
  14. entries each of which describe where that word occurs in the original files.
  15. A posting is a weight, doc_number (see the doc file), and character_position.
  16. This file is indexed with the dictionary (dct) file.  The terms are in
  17. alphabetical order.
  18.  *  index.doc -- this is a linear list of document-entries one for each
  19. document.  A document can be a complete file or a piece of a file (such as
  20. mail files that are the concatentation of many messages, each message is a
  21. document).  The information kept in each entry is:
  22.     filename_id:  position into the filename file (fn) of the filename
  23. for this document.
  24.     headline_id:  position in the headline file.
  25.     start_character: position in the file where this document starts
  26.     end_character: end position.  0 if complete file.
  27.     document_length: in characters
  28.     number_of_lines
  29.     date: time_t
  30.  *  index.fn -- list of the filenames in the database with the write-date
  31. of the file and the type of the file.  Type is a string.  Indexed by the
  32. position in the file, so this file can not be edited after the index is built.
  33.  *  index.hl -- list of the headlines.  Indexed by position.
  34.  *  index.dct -- dictionary file which is a 2 level b-tree.  The first block
  35. is pointers to the every 1000th entry in the rest of the dictionary file.
  36. Each entry is a fixed-length record of the word with the position into the
  37. rest of the file.  The rest of the file are blocks just like the first
  38. block, but each entry is the word plus the position of it in the inverted
  39. file (inv).  The whole dictionary is in alphabetical order.
  40.  *  index.src -- source description that is used to access the database.
  41. It is also returned as a response to the "help" query.  This file is not
  42. overwritten once it is created.  Therefore database maintainers should edit
  43. this file to add a good desciption of what that database contains.
  44.  *  index.status -- only the ram based seeker uses this to describe itself
  45. and get parameters from the user.
  46.  
  47.  
  48. INDEXING
  49.  
  50. A new index is built by parsing the input files, finding the words in it
  51. and creating the filename, headline, and doc tables at parse time.  The
  52. words are then passed to routines defined in irext.h which define the
  53. frontend/backend boundary.  
  54.  
  55. The serial indexer creates intermediate inv files starting at inv0 then
  56. inv1 etc.  These are created by accumulating the words in a memory
  57. hashtable.  Each invN file is in alphabetical order, so they can be merged
  58. easily into one inv file.  This merging is done logarithmically, so that it
  59. is fast.  Unfortunately, it means that just before the merging is done, the
  60. index occupies twice the space that it will finally.  
  61.  
  62. On the final merge, a dictionary file is produced by dumping the positions
  63. of the start of terms in the final inverted file.
  64.  
  65. Adding to an exising database is done by adding to the filename, headline,
  66. and doc tables as the parsing is done, but waiting to merge the new invN
  67. files into the old inv file until all the new merging is done.
  68. Theoretically it should be able to be done while always having the database
  69. usable.
  70.  
  71.  
  72. SEARCHING
  73.  
  74. A query is parsed for its seed words and relevant documents and is passed
  75. to a function search_word (defined in irext.h).  The backend does whatever
  76. it will do to search and set some state.  Then best_hit is called
  77. iteratively to find the documents that most closely matched the query.
  78. These results are used to look up headlines and filenames to hand back to
  79. the user.
  80.  
  81. The serial backend does this by loading the postings for a particular term
  82. and then adding it into a score array.  The score array has an entry for
  83. each document.  A document gets its score increased by containing terms in
  84. the query.
  85.  
  86.  
  87. Roughly the goals of this design were:
  88.   Make a flexible platform for experimentation
  89.   Portable
  90.   Low search overhead for fast startup and lightweight access
  91.   Usable in pieces for multiple search engines backends
  92.   Fast searching
  93.   Easy to implement
  94.   Size of the resulting database was not a priority
  95.  
  96.